from typing import List


class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        res = [-1] * len(nums)
        stack = []
        #第一次遍历nums
        for i, num in enumerate(nums):   
            while stack and num > nums[stack[-1]]:
                res[stack[-1]] = num
                stack.pop()
            stack.append(i)
        #此时stack仍有剩余，有部分数‘无下一个更大元素’待修正
        #第二次遍历nums
        for num in nums:
            #一旦stack为空，就表明所有数都有下一个更大元素，可以返回结果    
            if not stack:   
                return res
            while stack and num > nums[stack[-1]]:
                res[stack[-1]] = num
                stack.pop()
            #不要将已经有下一个更大元素的数加入栈，这样会重复赋值，只需对第一次遍历剩余的数再尝试寻找下一个更大元素即可
        #最后仍有部分最大数无法有下一个更大元素，返回结果
        return res  